package leetcode.L139;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {

    int[] memo;
    Set<String> set;
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        set = new HashSet<>(wordDict);
        return backtrack(s,0);
    }

    private boolean backtrack(String s,int startIndex){
        if(startIndex == s.length()) return true;
        if(memo[startIndex] == -1) return false;
        for(int i=startIndex; i<s.length(); i++){
            String sub = s.substring(startIndex, i+1);
            if(!set.contains(sub)){
                continue;
            }
            boolean backtrack = backtrack(s, i + 1);
            if(backtrack) return true;
        }
        memo[startIndex] = -1;
        return false;
    }
}